서로소 집합
서로 중복 포함된 원소가 없는 집합들
교집합이 없는 상태
서로소 집합을 표현하는 방법
- 연결 리스트 -> 대표를 갱신하려면 모든 원소를 갱신해야 한다
- 트리 -> 대표를 루트 노드로 표현할 수 있다
서로소 집합의 연산
Make-set
대표자 배열을 p[x] = x로 초기화
static void makeset(int x) {
p[x] = x;
}
Find-set
원소의 대표자를 얻어오는 연산
static int findset(int x) {
if(x == p[x]) {
return p[x];
}
return p[x] = findset(p[x]);
}
Union
두 원소의 대표자를 찾아 집합을 합치는 연산
static void union(int x, int y) {
// 하나를 기준으로 다른 하나의 부모를 합쳐주기
p[findset(y)] = findset(x);
}